package com.mamingchao.foundation.arraysort.buckesort.countsort;

/**
 * 计数排序 非比较排序，是桶排序思想的一种
 * 适合 数组量大，但是不重复的值范围比较小的 场景
 * 在数据库中，不重复的数据记录叫 （基数？），大概就是 数据中 不重复的数据的个数 / 原始数据长度
 *
 * 比如万人企业中，按年龄排序（年龄 0 - 60）
 * 比如 高考中 高考成绩排名（高考成绩 0- 750）
 *
 * 计数排序，如果里面没有0的值，会比 有0的的 复杂
 *
 * 两个问题：1、如何处理 值的起始范围不是0，比如100-150？
 * 2、这个算法是不稳定的，写一个稳定的算法
 *
 * Created by mamingchao on 2021/3/19.
 */
public class CountSort{

    public static void main(String[] args) {

        int[] arr ={ 1,2,1,1,0,0,3,2,2,2,3};
        sort(arr,4);
    }

    /**
     *
     * @param arr 原始数组
     * @param limit 数据 基数值（不重复的数据个数）
     */
    public static void sort(int[] arr,int limit){
        int[] count = new int[limit];

        for (int i = 0; i < arr.length; i++) {
            count[arr[i]] ++;
        }

        int[] sortedArr = new int[arr.length];

        int k = 0;
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count[i]; j++) {
                sortedArr[k++] = i;
            }
        }

        printArr(sortedArr);
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
